/*
 * @lc app=leetcode.cn id=78 lang=cpp
 *
 * [78] 子集
 *
 * https://leetcode-cn.com/problems/subsets/description/
 *
 * algorithms
 * Medium (80.47%)
 * Likes:    1615
 * Dislikes: 0
 * Total Accepted:    435.3K
 * Total Submissions: 540.9K
 * Testcase Example:  '[1,2,3]'
 *
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * -10 
 * nums 中的所有元素 互不相同
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     vector<int> path;
//     vector<vector<int>> res;
//     void backtracking(const vector<int>& nums, int startIndex) {

//         // 收集每一个结点
//         res.push_back(path);

//         if(startIndex > nums.size()) return;

//         for (int i = startIndex; i < nums.size(); i++) {
//             path.push_back(nums[i]);
//             backtracking(nums, i+1);
//             path.pop_back();
//         }
//     }

// 复盘
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int> nums, int startIndex) {
        // 不是说走到叶子结点再回收信息，
        // 而是，path被push进去的每一个结点，都要回收结果
        res.push_back(path);

        // 这一点表明走到了叶子结点，不能再往下了，再往下已经没有了结点
        // 算是递归终止的一个条件
        // 但是这个条件可以不需要，因为当i= startIndex > nums.size()的时候
        // 下边的for循环不会进行，直接就出程序了。
        // 但是加上可以提示终止条件。
        if(startIndex > nums.size()) return;

        for(int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }

    }


public:
    vector<vector<int>> subsets(vector<int>& nums) {
        path.clear();
        res.clear();
        backtracking(nums, 0);
        return res;
    }
};
// @lc code=end

